Heretofore, a standard coding system for a moving picture, such as ITU-T H.26x and MPEG series, has been known as a coding system for a moving picture. In such an image coding system, image data (spatial image data) represented by spatial coordinates undergoes an orthogonal transform and is transformed into image data (frequency image data) represented by spatial frequencies. The orthogonal transform as described above makes it possible to remove a redundancy as to a spatial change from a frame image serving as an object to be coded, and efficiency of data compression by an image coding and the like are enhanced.
As an orthogonal transform applied to image data, DCT (discrete cosine transform) is mainly used from a viewpoint of a balance between the compression efficiency and a package load, popularization of an exclusive LSI and the like. The DCT is carried out for the spatial image data, and thus a plurality of DCT coefficients are generated as orthogonal transform coefficients, which are frequency image components in the frequency image data.
Moreover, the orthogonal transform coefficients generated by the orthogonal transform such as the DCT further undergo variable-length coding, and become coded data as compressed data for use in image transmission. As one of such variable-length coding methods, arithmetic coding (AC) is used.
In general, in the case of carrying out the arithmetic coding of an information source string (symbol string) formed by combining plural types of symbols, first, certain sections are allocated to the respective symbols in accordance with the appearance probabilities of the symbols on a number line (probability number line) of [0.0, 1.0). In this case, one representing correspondence relationships between the symbols and the sections on the number line is called a probability table. When the information source string undergoes the variable-length coding by the arithmetic coding, code words expressing the information source string on the number line is generated by referring to this probability table.
Here, the arithmetic coding will be described with reference to FIGS. 1 to 3. Specifically, a character string “ARITHMETIC” will be cited as the information source string to be coded, and the arithmetic coding thereof will be exemplified.
Eight types of characters (symbols), which are A, C, E, H, I, M, R and T, appear in the above-described information source string. As shown in the table of FIG. 1, sections are allocated to these characters on the number line (probability number line) of [0.0, 1.0) such that section lengths proportional to the appearance probabilities of the respective characters in the character string can be obtained. The table shown in FIG. 1, which represents these correspondence relationships between the characters and the sections on the number line, becomes a probability table for use in the arithmetic coding.
FIG. 2 is a diagram illustrating the coding of the character string “ARITHMETIC” by use of the probability table shown in FIG. 1. In the arithmetic coding, a section reduction operation based on the probability table is sequentially carried out for the respective symbols included in the information source string, thus generating code words formed by coding the information source string.
In the example shown in FIG. 2, first, the probability table shown in FIG. 1 is referred to for the first character “A” of the character string “ARITHMETIC” to be coded, and the section [0, 1) on the number line is divided into eight sections corresponding to the respective characters. Then, the section is reduced to the section [0.0, 0.1) corresponding to the character “A” among the eight sections. Next, the probability table is referred to for the second character “R”, and the section [0.0, 0.1) is divided into eight sections. Subsequently, among these sections, the section is reduced to the section [0.07, 0.08) corresponding to the character “R”.
Hereinafter, the coding operations by the section reduction are carried out sequentially for each of the characters. Then, in the section [0.0757451536, 0.0757451552) on the number line finally obtained, a numerical value “0.0757451536” within the section is generated as a code word obtained by performing the arithmetic coding of the character string “ARITHMETIC”.
FIG. 3 is a table showing decoding of the code word “0.0757451536” obtained by use of the probability table shown in FIG. 1 to the character string “ARITHMETIC”.
In the example shown in FIG. 3, the probability table shown in FIG. 1 is referred to for the code word “0.0757451536” to be decoded, and the section [0.0, 0.1) having a section length of 0.1 in which the code word is included is specified. Then, the character “A” corresponding to the specified section is outputted as the first character, and a new code word “0.757451536” is generated by (code word—lower limit)/(section length). Next, the probability table is referred to for the code word “0.757451536”, and a section [0.7, 0.8) having a section length of 0.1 in which the code word is included is specified. Then, the character “R” corresponding to the specified section is outputted as the second character, and a new code word “0.57451536” is generated.
Hereinafter, the decoding operations are sequentially carried out for the code words. Then, the character string “ARITHMETIC” is restored from the code word “0.0757451536” which underwent the arithmetic coding.
As described above, in the variable-length coding of the information source string by use of the arithmetic coding, the symbols included in the information source string and the sections on the number line are allowed to correspond to each other, thus making it possible to express an arbitrary information source string by the code words on the number line of [0.0, 1.0). Moreover, the probability table allowing the symbols and the sections to correspond to each other is set in accordance with the appearance probabilities of the respective symbols, whereby the variable-length coding of the information source string can be performed effectively and the efficiency of data compression by the coding can be enhanced.